package com.adamjwh.pratice.offer;

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
 */
public class InversePairsNum {
    public int InversePairs(int [] array) {
        if(array == null || array.length <= 0) {
            return 0;
        }

        int[] copy = new int[array.length];
        for(int i=0; i<array.length; i++) {
            copy[i] = array[i];
        }

        int p = InversePairsCore(array, copy, 0, array.length-1);

        return p;
    }

    private int InversePairsCore(int[] arr, int[] copy, int low, int high) {
        if(low == high) {
            return 0;
        }

        int mid = (low + high) >> 1;
        int leftCount = InversePairsCore(arr, copy, low, mid) % 1000000007;
        int rightCount = InversePairsCore(arr, copy, mid+1, high) % 1000000007;

        int count = 0;
        int i = mid, j = high;
        int locCopy = high;

        while (i >= low && j > mid) {
            if(arr[i] > arr[j]) {
                count += j-mid;
                copy[locCopy--] = arr[i--];

                if(count >= 1000000007) {
                    count %= 1000000007;
                }
            } else {
                copy[locCopy--] = arr[j--];
            }
        }

        for (; i>=low; i--) {
            copy[locCopy--] = arr[i];
        }

        for (; j>mid; j--) {
            copy[locCopy--] = arr[j];
        }

        for (int s=low; s<=high; s++) {
            arr[s] = copy[s];
        }

        return (leftCount + rightCount + count) % 1000000007;
    }
}
